package com.example.demo.algorithm.lru_lfu;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 *
 * 参考：https://juejin.cn/post/7070386659199549454#heading-0
 * 使用双哈希表进行实现，一个哈希表用于存储对应的数据，另一个哈希表用于存储数据被使用次数和对应的数据。
 * @param <K>
 * @param <V>
 */
public class MyLfuCache <K,V>{

    class Node{
        K key;
        V value;
        int usedCount = 1;

        Node(K key,V value){
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private int minUsedCount;
    private Map<K,Node> map;
    private Map<Integer, List<Node>> usedCountMap;

    public MyLfuCache(int capacity){
        this.capacity = capacity;
        this.minUsedCount = 1;
        this.map = new HashMap<>();
        this.usedCountMap = new HashMap<>();
    }

    public V get(K key){
        Node node = map.get(key);
        if(node == null){
            return null;
        }
        addUsedCount(node);
        return node.value;
    }

    public V put(K key,V value){
        Node node = map.get(key);
        if(node != null){
            V oldValue = node.value;
            node.value = value;
            addUsedCount(node);
            return oldValue;
        }else{
            //数据不存在，判断链表是否满了
            if(map.size() == capacity){
                List<Node> list = usedCountMap.get(minUsedCount);
                Node delNode = list.get(0);
                list.remove(delNode);
                map.remove(delNode.key);
            }
            //新增数据并放到数据频率为1的数据链表中
            Node newNode = new Node(key,value);
            map.put(key,newNode);
            List<Node> list = usedCountMap.get(1);
            if(list == null){
                list = new LinkedList<>();
                usedCountMap.put(1,list);
            }
            list.add(newNode);
            minUsedCount = 1;
            return null;
        }
    }

    private void addUsedCount(Node node) {
        List<Node> oldList = usedCountMap.get(node.usedCount);
        oldList.remove(node);

        //更新最小数据频率
        if(minUsedCount == node.usedCount && oldList.isEmpty()){
            minUsedCount++;
        }

        node.usedCount++;

        List<Node> set = usedCountMap.get(node.usedCount);
        if(set == null){
            set = new LinkedList<>();
            usedCountMap.put(node.usedCount,set);
        }
        set.add(node);
    }

}
